package leetcode_1_200;


import java.util.*;

public class LeeCode_133 {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        List<Node> l1 = new ArrayList<>();
        l1.add(n2);
        l1.add(n4);
        List<Node> l2 = new ArrayList<>();
        l2.add(n1);
        l2.add(n3);
        List<Node> l3 = new ArrayList<>();
        l3.add(n2);
        l3.add(n4);
        List<Node> l4 = new ArrayList<>();
        l4.add(n1);
        l4.add(n3);
        n1.neighbors = l1;
        n2.neighbors = l2;
        n3.neighbors = l3;
        n4.neighbors = l4;
        Node copy = cloneGraph(n1);
    }

    private static Node cloneGraph(Node node) {
        if (node == null)
            return null;
        Node ans = new Node();
        Map<Integer, Node> exists = new HashMap<>();
        f(node, ans, exists);
        return ans;
    }
    private static void f(Node root, Node node, Map<Integer, Node> exists){
        node.val = root.val;
        exists.put(node.val, node);
        List<Node> rootNs = root.neighbors;
        List<Node> nodeNs = new ArrayList<>(rootNs.size());
        node.neighbors = nodeNs;
        for (Node rootN : rootNs) {
            if (!exists.containsKey(rootN.val)) {
                Node newN = new Node();
                f(rootN, newN, exists);
                nodeNs.add(newN);
                exists.put(newN.val, newN);
            }else {
                nodeNs.add(exists.get(rootN.val));
            }
        }
    }

    private static class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}
